package com.mango.algorithm.sort;

import java.util.Arrays;

/**
 * 选择排序
 * 空间复杂度：只需要一个临时空间做交换用，为O(1)
 * 时间复杂度：由于需要2个循环，则为O(n²)
 *
 * 思路描述：
 * 每一次选择数组中最小的值，放到最左边
 *
 * 例子
 * old:[13, 7, 4, 6, 9, 24, 12, 3, 5, 2]
 * select=2,swap 2 to 13
 * 0)[2, 7, 4, 6, 9, 24, 12, 3, 5, 13]
 * select=3,swap 3 to 7
 * 1)[2, 3, 4, 6, 9, 24, 12, 7, 5, 13]
 * select=5,swap 5 to 6
 * 3)[2, 3, 4, 5, 9, 24, 12, 7, 6, 13]
 * select=6,swap 6 to 9
 * 4)[2, 3, 4, 5, 6, 24, 12, 7, 9, 13]
 * select=7,swap 7 to 24
 * 5)[2, 3, 4, 5, 6, 7, 12, 24, 9, 13]
 * select=9,swap 9 to 12
 * 6)[2, 3, 4, 5, 6, 7, 9, 24, 12, 13]
 * select=12,swap 12 to 24
 * 7)[2, 3, 4, 5, 6, 7, 9, 12, 24, 13]
 * select=13,swap 13 to 24
 * 8)[2, 3, 4, 5, 6, 7, 9, 12, 13, 24]
 * result:[2, 3, 4, 5, 6, 7, 9, 12, 13, 24]
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] nums = {13,7,4,6,9,24,12,3,5,2};
        System.out.println("old:"+ Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums)));
    }
    // 选择排序
    public static int[] sort(int[] nums){
        int select = 0;
        for(int i=0;i<nums.length;i++){
            select = i;
            for(int j=i;j<nums.length;j++){
                if(nums[j]<nums[select]){
                    select = j;
                }
            }
            if(select != i) {
                System.out.println("select="+nums[select]+",swap "+nums[select]+" to "+ nums[i]);
                swap(nums, i, select);
                System.out.println(i + ")" + Arrays.toString(nums));
            }
        }
        return nums;
    }
    // 交换数组下标
    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
